
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1749. -- [usaco2005 open]Landscaping -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1749: [usaco2005 open]Landscaping</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>13&nbsp;&nbsp;<span class=green>Solved: </span>9<br>[<a href='submitpage.php?id=1749'>Submit</a>][<a href='problemstatus.php?id=1749'>Status</a>][<a href='bbs.php?id=1749'>Discuss</a>]</center><h2>Description</h2><div class=content>
Farmer John is making the difficult transition from raising mountain
goats to raising cows.  His farm, while ideal for mountain goats,
is far too mountainous for cattle and thus needs to be flattened
out a bit. Since flattening is an expensive operation, he wants to
remove the smallest amount of earth possible.

The farm is long and narrow and is described in a sort of two-dimensional
profile by a single array of N (1 <= N <= 1000) integer elevations
(range 1..1,000,000) like this:

1 2 3 3 3 2 1 3 2 2 1 2,

which represents the farm's elevations in profile, depicted below
with asterisks indicating the heights:

    * * *     *
  * * * * *   * * *   *
* * * * * * * * * * * *
1 2 3 3 3 2 1 3 2 2 1 2

A contiguous range of one or more equal elevations in this array
is a "peak" if both the left and right hand sides of the range are
either the boundary of the array or an element that is lower in
elevation than the peak. The example above has three peaks.

Determine the minimum volume of earth (each unit elevation reduction
counts as one unit of volume) that must be removed so that the
resulting landscape has no more than K (1 <= K <= 25) peaks.  Note
well that elevations can be reduced but can never be increased.

If the example above is to be reduced to 1 peak, the optimal solution
is to remove 2 + 1 + 1 + 1 = 5 units of earth to obtain this set
of elevations:

    * * *     -
  * * * * *   - - -   -
* * * * * * * * * * * *
1 2 3 3 3 2 1 1 1 1 1 1

where '-'s indicate removed earth.

</div><h2>Input</h2><div class=content>
* Line 1: Two space-separated integers: N and K

* Lines 2..N+1: Each line contains a single integer elevation. Line
        i+1 contains the elevation for index i.

</div><h2>Output</h2><div class=content>
* Line 1: The minimum volume of earth that must be removed to reduce
        the number of peaks to K.

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata><br />
12 1<br />
1<br />
2<br />
3<br />
3<br />
3<br />
2<br />
1<br />
3<br />
2<br />
2<br />
1<br />
2<br />
<br />
INPUT DETAILS:<br />
<br />
This is the example used above.<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata><br />
5<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Gold'>Gold</a></p></div><center>[<a href='submitpage.php?id=1749'>Submit</a>][<a href='problemstatus.php?id=1749'>Status</a>][<a href='bbs.php?id=1749'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
